1. Field of the Invention
This invention relates to caches of computer systems. In particular, this invention relates to the efficient allocation of cache memory space in a computer system.
2. Description of the Related Art
In a simple cache space allocation scheme for a multi-level-cache computer system having a small first-level cache and a larger second-level cache, all data structures are automatically cached in both levels of caches. If the size of a data structure is larger than the smaller lower-level cache, i.e., the data structure does not fit into the lower-level cache, the data structure is replaced from the lower-level cache. Hence, if the data structure is smaller than the larger higher-level cache, most of the content of the data structure will remain in the higher-level cache.
Unfortunately, while some data structures are accessed frequently, other data structures are accessed only once and it is not easy to predict future access(es) of a particular structure without some statistical analysis and/or knowledge of the computer program which owns the data structure(s). For example, a computer program may use a large array by accessing each element of the array once. Each element is then used in a fairly complicated computation involving temporary variables. In this example, caching every element of the large array will not substantially increase the computational speed. In contrast, caching the temporary variables will result in a faster execution of the program.
Hence, although the above-described scheme for allocating space in a multi-level cache is simple, the scheme is based solely on the size of the data structure, and hence is inefficient because a substantial number of data structures are unnecessarily cached. Excessive caching causes other useful data structures to be replaced prematurely, i.e., ejected from the cache(s) before subsequent accesses.
Since cache memories are not infinitely large, efficient allocation of limited cache resources is needed in order to maximize usage of the caches and minimize overall access time to data. Thus there is a need for an efficient mechanism to select data structures for caching which also optimizes the allocation of cache memory space in a multi-level-cache computer system.